Linux Cubed Series 8: LINUX Games/Linux Cubed Series 8 - LINUX Games.iso/games/x11/rpg/crossfir.001/crossfir~/eutl/chain-hash/chain-hash.c

C/C++ Source or Header | 1994-09-19 | 5KB | 194 lines

#include <stdio.h>

#include <chain-hash.h>
#include <xmalloc.h>
#include <libc.h>
extern HashFunction __eutl_default_hash;

static ErrorFunction Erf = LongJmpErrorFunction;

char *chainhash_packagever = "Chain Hashing V1.0";
char *chainhash_Ebadinsert = "Bad Insertion";
char *chainhash_Ebadlookup = "Bad Lookup";

/* Save the malloc overhead of having to malloc space for the
   key and the data -- yea, probably a minor optimization */

typedef struct __Bucket {
  xint keylen,datalen;
  struct __Bucket *next;
  unsigned char stuff[1];
} Bucket;

/* PAD8 computes the number of bytes needed to round the value up to the
   next multiple of 8 */
/*
#define PAD8(bytes) ((8 - ((unsigned int) (bytes) %8)) % 8)
*/
#define PAD8(bytes) ((8 - ((unsigned int) (bytes) & 0x7)) & 0x7)
#define KEYOFBUCKET(b) ((b)->stuff)
#define DATAOFBUCKET(b) ((b)->stuff + (b)->keylen + PAD8((b)->keylen))
#define BUCKETMALLOCSIZE(klen,dlen) \
   (sizeof(Bucket) + (klen) + PAD8(klen) + (dlen) - 1)

struct __chain_hash {
  Bucket **buckets;
  HashFunction hfunc;
  UM32B nbuckets;
  HashStatistics stats;
};

static UM32B prime_list[] = {
  97, 191, 433, 821, 1543, 3313, 6091, 12289, 24281, 48397, 100169,
  213397, 487651, 882491, 1179589, 2471093
};

#define NPRIMES (sizeof(prime_list)/sizeof(UM32B))

HashTable CreateHashTable(long tablesize,HashFunction hfunc)
{
  HashTable ret;

  if (hfunc == NULL)
    hfunc = __eutl_default_hash;
  if (tablesize<=0) {
    int l;

    tablesize = (- tablesize);

    for(l=0;l<NPRIMES;l++) {
      if (prime_list[l] > tablesize)
    break;
    }
    if (l==NPRIMES)
      l = NPRIMES-1;
    tablesize = prime_list[l];
  }
  ret = (HashTable)xbzmalloc(sizeof(struct __chain_hash));
  ret->buckets = (Bucket **)xbzmalloc(sizeof(Bucket *)*tablesize);
  ret->stats.nbuckets = tablesize;
  ret->nbuckets = tablesize;
  ret->hfunc = hfunc;

  return ret;
}

void DestroyHashTable(HashTable table,DestroyBucketFunc func)
{
  xint l;
  Bucket *j,*nextj;

  if (func != NULL) {
    for(l=0;l<table->nbuckets;l++) {
      for(j=table->buckets[l];j != NULL;j=nextj) {
    nextj = j->next;
    func(KEYOFBUCKET(j),j->keylen,DATAOFBUCKET(j),j->datalen);
    free(j);
      }
    }
  } else {
    for(l=0;l<table->nbuckets;l++) {
      for(j=table->buckets[l];j != NULL;j=nextj) {
    nextj = j->next;
    free(j);
      }
    }
  }
}

void HashInsert(HashTable table,void *key,xint keylen,void *data,xint datalen)
{
  UM32B hval = table->hfunc(key,keylen) % table->nbuckets;
  Bucket *newbucket;

  for(newbucket=table->buckets[hval];
      newbucket != NULL;
      newbucket = newbucket->next) {
    if ((keylen == newbucket->keylen) &&
    (bcmp(KEYOFBUCKET(newbucket),key,keylen)==0)) {
      Erf(chainhash_packagever,chainhash_Ebadinsert,
      "Hash entry already exists with specified key.");
    }
  }
  table->stats.nentries++;
  newbucket = (Bucket *)xmalloc(BUCKETMALLOCSIZE(keylen,datalen));
  newbucket->keylen = keylen;
  newbucket->datalen = datalen;
  bcopy(key,KEYOFBUCKET(newbucket),keylen);
  bcopy(data,DATAOFBUCKET(newbucket),datalen);
  if (table->buckets[hval] == NULL) {
    table->stats.bucketsused++;
  }
  newbucket->next = table->buckets[hval];
  table->buckets[hval] = newbucket;
}

void SHashInsert(HashTable table,char *key,void *data,xint datalen)
{
  HashInsert(table,key,strlen(key)+1,data,datalen);
}

void HashOverwrite(HashTable table,void *key,xint keylen,void *data,xint datalen)
{
  UM32B hval = table->hfunc(key,keylen) % table->nbuckets;
  Bucket *oldbucket;

  for(oldbucket=table->buckets[hval];
      oldbucket != NULL;
      oldbucket = oldbucket->next) {
    if ((keylen == oldbucket->keylen) &&
    (bcmp(KEYOFBUCKET(oldbucket),key,keylen)==0)) {
      break;
    }
  }
  if (oldbucket == NULL) {
    /* read oldbucket in this part of the if as newbucket */
    table->stats.nentries++;
    oldbucket = (Bucket *)xmalloc(BUCKETMALLOCSIZE(keylen,datalen));
    oldbucket->keylen = keylen;
    oldbucket->datalen = datalen;
    bcopy(key,KEYOFBUCKET(oldbucket),keylen);
    bcopy(data,DATAOFBUCKET(oldbucket),datalen);
    if (table->buckets[hval] == NULL) {
      table->stats.bucketsused++;
    }
    oldbucket->next = table->buckets[hval];
    table->buckets[hval] = oldbucket;
  } else {
    oldbucket = (Bucket *)xrealloc(oldbucket,BUCKETMALLOCSIZE(keylen,datalen));
    oldbucket->datalen = datalen;
    bcopy(data,DATAOFBUCKET(oldbucket),datalen);
  }
}

void SHashOverwrite(HashTable table,char *key,void *data,xint datalen)
{
  HashOverwrite(table,key,strlen(key)+1,data,datalen);
}

void *HashLookup(HashTable table,void *key,xint keylen)
{
  UM32B hval = table->hfunc(key,keylen) % table->nbuckets;
  Bucket *l;

  for(l=table->buckets[hval]; l != NULL; l = l->next) {
    if ((keylen == l->keylen) &&
    (bcmp(KEYOFBUCKET(l),key,keylen)==0)) {
      return DATAOFBUCKET(l);
    }
  }
  Erf(chainhash_packagever,chainhash_Ebadlookup,
      "Hash entry with specified key doesn't exist.");
  return NULL;
}

void *SHashLookup(HashTable table,char *key)
{
  return HashLookup(table,key,strlen(key)+1);
}

HashStatistics *GetStatistics(HashTable table)
{
  return &table->stats;
}